package com.jiashihui.schema_lgorithm.arithmetic.recursion;

import lombok.extern.slf4j.Slf4j;

/**
 * @author jiashihui
 * @describe: 递归
 * @date 2019/02/18
 *
 * 当函数直接或者间接调用自己时，则发生了递归。
 *
 * 递归构造包括两个部分：
 * 定义递归头。什么时候不调用自身方法，如果没有头，将陷入死循环。
 * 递归体。什么时候需要调用自身方法。
 */
@Slf4j
public class Recursion {
    private static int a = 0;

    public static void main(String[] args) {

        // 计算阶乘
        log.info("result：" + factorial(3));

        // 二分查找
        // 注意：二分查找的数组一定是有序的
        int[] array = {3, 7, 8, 9, 12, 15, 22, 25, 33, 50, 68};
        int index = search(array, 33, 0, array.length -1);
        log.info("index:" + index);

        move(2, "A", "B","C");

    }

    // 计算 阶乘
    public static long factorial(int n){
        //递归体
        if(n == 1){
            return 1;
        }else{
            //递归头
            return n*factorial(n-1);
        }
    }

    // 递归
    public static void test01(){
        a++;
        System.out.println("test——"+a);
        if(a <= 10){//递归头
            test01();
        }else{//递归体
            System.out.println("over!");
        }
    }

    /**
     * 二分查找
     * 找到目标值返回数组下标，找不到返回-1
     * @param array 查找数组
     * @param key 目标值
     * @return
     */
    public static int search(int[] array, int key, int low, int high){
        int mid = (high-low)/2 + low;
        if(key == array[mid]){
            return mid;
        }else if(low > high){
            return -1;
        } else {
            // 分治策略
            if(key < array[mid]){
                return search(array, key, low, mid-1);
            } else {
                return search(array, key, mid + 1, high);
            }
        }
    }

    /**
     * 汉诺塔问题
     * @param dish 盘子个数(也表示名称)
     * @param from 初始塔座
     * @param temp 中介塔座
     * @param to   目标塔座
     */
    public static void move(int dish,String from,String temp,String to){
        if(dish == 1){
            System.out.println("将盘子"+dish+"从塔座"+from+"移动到目标塔座"+to);
        }else {
            move(dish - 1, from, to, temp);
            System.out.println("将盘子" + dish + "从塔座" + from + "移动到目标塔座" + to);
            move(dish - 1, temp, from, to);
        }
    }
}
